/*
题目链接：https://leetcode.cn/problems/numbers-with-repeated-digits/description/
1012. 至少有1位重复的数字-困难
完成日期：2024/10/6
数位DP
*/
class Solution {
public:
    int a[10];
    long long dp[10][1<<11];
    long long dfs(int po,int l,int le,int s){
        if(po==-1) return 1;
        if(!l&&!le&&dp[po][s]!=-1) return dp[po][s];
        int u=l?a[po]:9;
        int ans=0;
        for(int i=0;i<=u;i++){
            if(le&&i==0) ans+=dfs(po-1,l&&i==u,1,s);
            else{
                if(s&1<<i) continue;
                else ans+=dfs(po-1,l&&i==u,le&&i==0,s|1<<i);
            }
        }
        if(!le&&!l) dp[po][s]=ans;
        return ans;
    }
    int solve(int x){
        int n=x;
        int pos=0;
        while(x){
            a[pos++]=x%10;
            x/=10;
        }
        return n+1-dfs(pos-1,1,1,0);
    }
    int numDupDigitsAtMostN(int n) {
        memset(dp,-1,sizeof dp);
        return solve(n);

    }
};